var trace = function(x) {
	document.write('<pre style="font:11px monospace; background-color:#eee;padding:3px;margin:5px 0;">' + html_escape(sprintf.apply(this, arguments)) + '</pre>');
};


var Stream = function(str) {
	if (str !== undefined)
		this.load(str);
};
Stream.prototype = {
	EOF: -1,
	load: function(str) {
		this.source = str;
		this.length = this.source.length;
		this.reset();
	},
	eof: function() {
		return this.char === this.EOF;
	},
	reset: function() {
		this.pos = 0;
	},
	getch: function() {
		if (this.pos >= this.length)
			return this.char = this.EOF;
		return this.char = this.source[this.pos++];
	}
};

var last_rule_id = 1;

var lex_rule = function(str, f) {
	var out = [];
	var i, max = str.length;
	for (i = 0; i < max; ++i)
		out[i] = {};
	//var action = function() { f(str) };
	var action = f;
	//action.toString = function() { return '[' + str + ']' };
	out[out.length] = { action: action };
	for (i = 0, max = out.length - 1; i < max; ++i)
		out[i][str[i]] = out[i + 1];
	return out[0];
};


var lex_merge = function(r1, r2) {
	//r2 = objoin({}, r2);
	
	if (r2.action && !r1.action) {
		r1.action = r2.action;
	}

	for (var i in r2) {
		if (i.length > 1 && i != 'any') continue;
		if (!r1[i]) {
			//r1[i] = objoin({}, r2[i]);
			r1[i] = r2[i];
			continue;
		}
		lex_merge(r1[i], r2[i]);
	}
	
	if (r2.any) {
		for (var i in r1) {
			if (i.length > 1) continue;
			lex_merge(r1[i], r2.any);
		}
	}

	
	
	return r1;
};


var lex_run = function(initial, input) {
	var s, state = initial;
	var c;
	//console.dir(state);
	var i = 0, max = input.length;
	yytext = '';
	var d;
	var last_accepting_pos = 0, last_accepting_state = initial;
	var last_accepting_yytext = '';
	var action;
	var x;
	var yytext_pos = 0;
	
	var cnt = 0, cnt2 = 0;
	var _yytext = '';
	var _yytext_len = 0;
	var buf, buf_size;
	//var BUFFER_SIZE = 100;
	
	buf = input;
	buf_size = buf.length;
	/*
	var input_position = 0;
	var read = function(input, N){
		//var N = 100;
		var result = input.substr(input_position, N);
		input_position += result.length;
		return result;
	};
	
	buf = read(input, 1000);
	buf_size = buf.length;
	*/
	
	//debugger;

	while (true) {
		if (cnt++ > 100000) { alert('hang up'); return; }		
		
		if (i >= max) break;
		
		state = initial;
		//s = state;
		_yytext = '';
		//_yytext_len = 0;

		
		//return;

		//XXX
		while (s = state[c=buf[i]] || state.any) {
			++cnt2;
			state = s;
			//trace('current character: ' + c + ' (i=' + i + ')');
			_yytext += c;
			//_yytext[_yytext.length] = c;
			//_yytext.push(c);
			//_yytext[_yytext_len++] = c;
			++i;
			if (state.action) {
				last_accepting_state = state;
				last_accepting_pos = i;
				//last_accepting_yytext = _yytext;
			}
			if (i >= max)
				break;
		}
		//trace('i:'+i+', max:'+max+', state:'+Object.getOwnPropertyNames(state)+', _yytext:'+_yytext);
		//alert(dump(state));
		if (!state.action) {
			_yytext = _yytext.substr(i - last_accepting_pos - 1);
			//_yytext.splice(i - last_accepting_pos);
			//_yytext = last_accepting_yytext;
			state = last_accepting_state;
			i = last_accepting_pos;
		}
		//trace('i:'+i+', max:'+max+', state:'+Object.getOwnPropertyNames(state)+', _yytext:'+_yytext);

		//yytext = buf.substr(yytext_pos, i - yytext_pos);
		//yytext = 'function';
/*
		if (i >= 200) {
			buf = buf.substr(i);
			buf += read(input, 1000);
			buf_size = buf.length;
			if (!buf_size)
				return;
			i = 0;
		}
*/

		
		if (state.action && state.action !== lex_empty_action) {
			yytext = _yytext;
			x = state.action();
			if (x)
				trace('action: ' + x);
		}
		
		//_yytext.splice(0);
		
	}
/*	
	window.setTimeout(function(){
		alert('text size='+input.length+', cnt='+cnt+', cnt2='+cnt2);
	}, 10);
*/	
};


// asdfjsdkfjsdkfjskdjfskdjfhsjkdfhkwjerhwsasdfjsdkfjsdkfjskdjfskdjfhsjkdfhkwjerhws

var add_range = function(assoc, start, end) {
	for (var i = start.charCodeAt(0), max = end.charCodeAt(0); i <= max; ++i)
		assoc[String.fromCharCode(i)] = 1;
	return assoc;
};

var parse_range = function(stream) {
	var c, c0;
	var assoc = {};

stream_loop:	
	while (true) {
		c = stream.getch();
		if (stream.eof())
			break;
		switch (c) {
			case ']':
				break stream_loop;
			default:
				assoc[c] = 1;
				break;
			case '.':
				assoc.any = 1;
				break;
			case '-':
				if (c0 === undefined)
					assoc[c] = 1;
				else {
					c = stream.getch();
					add_range(assoc, c0, c);
				}
				break;
			case '\\':
				c = stream.getch();
				switch (c) {
					case 'w':
						add_range(assoc, 'a', 'z');
						add_range(assoc, 'A', 'Z');
						add_range(assoc, 'а', 'я');
						add_range(assoc, 'А', 'Я');
						assoc['_'] = 1;
						//add_range(assoc, 'A', 'Z');
						break;
					case 'd': add_range(assoc, '0', '9'); break;
					case 's': assoc[' '] = assoc['\t'] = 1; break;
					case 't': assoc['\t'] = 1; break;
					case 'n': assoc['\n'] = 1; break;
					case 'r': assoc['\r'] = 1; break;
					default: assoc[c] = 1; break;
				}
				break;
		}
		c0 = c;
	}
	var out = [];
	for (var i in assoc)
		if (assoc[i] == 1)
			out[out.length] = i;
	out.sort();
	return out;
	
	//throw "']' expected in regexp";
};


// asdfjkjkjkjkjretjfoeijccimwieorumwerwerieriweur

var parse_re = function(source) {
	var group = 0;
	var rec = function(stream, result) {
		var c = stream.getch();
		switch (c) {
			case stream.EOF:
				return result;
			default:
				result.push(['C', c]);
				return rec(stream, result);
			case '\\':
				c = stream.getch();
				switch (c) {
					case 'w': result.push(['R', parse_range(new Stream('a-zA-Z_а-яА-Я'))]); break;
					case 'd': result.push(['R', parse_range(new Stream('0-9'))]); break;
					case 's': result.push(['R', parse_range(new Stream(' \t'))]); break;
					case 'r': result.push(['C', '\r']); break;
					case 'n': result.push(['C', '\n']); break;
					default:  result.push(['C', c]); break;
				}
				return rec(stream, result);
			case '|':
				var x = rec(stream, []);
				return [['|', result, x]];
			case '[':
				var r = parse_range(stream);
				result.push(['R', r]);
				return rec(stream, result);
			case '(':
				var g = ++group;
				var x = rec(stream, []);
				result.push(['G', x, g]);
				return rec(stream, result);
			case ')':
				//return result.length == 1 ? result[0] : result;
				return result;
			case '?':
				result.push(['?', [result.pop()]]);
				return rec(stream, result);
			case '+':
				result.push(['+', [result.pop()]]);
				return rec(stream, result);
			case '*':
				result.push(['*', [result.pop()]]);
				return rec(stream, result);
			case '.':
				result.push(['.']);
				return rec(stream, result);
		}
	};
	if (source.constructor === RegExp)
		source = source.source;
	//alert(source);
	var stream = new Stream(source);
	var result = rec(stream, []);
	//result.source = source;
	return result;
};


var re_to_string = function(re) {
	var out = [];
	var hd;
	
	for (var i = 0, max = re.length; i < max; ++i) {
		hd = re[i];
		
		switch (hd[0]) {
			case '.':
				out[out.length] = '.';
				break;
				
			case 'C':
				out[out.length] = re_escape(hd[1]);
				break;

			case 'G':
				out[out.length] = '(';
				out[out.length] = re_to_string(hd[1]);
				out[out.length] = ')';
				break;

			case 'R':
				var cc = hd[1], a0, a1, a2, a3;
				//alert(cc);
				if (cc.length == 1) {
					switch (cc[0]) {
						case 'any': out[out.length] = '.'; break;
						default: out[out.length] = re_escape(cc[0]); break;
					}
					break;
				}
				
				out[out.length] = '[';
				for (var j = 0, jmax = cc.length; j < jmax; ++j) {
					if (cc[j] == 'any') { out[out.length] = '.'; continue; }
					if (j + 3 < jmax) {
						a0 = cc[j+0].charCodeAt(0);
						a1 = cc[j+1].charCodeAt(0);
						a2 = cc[j+2].charCodeAt(0);
						a3 = cc[j+3].charCodeAt(0);
						if (a1 == a0 + 1 && a2 == a1 + 1 && a3 == a2 + 1) {
							out[out.length] = re_escape(cc[j]) + '-';
							for (var n = a1; j + 1 < jmax && n == cc[j + 1].charCodeAt(0); ++j, ++n);
						}
					}
					out[out.length] = re_escape(cc[j]);
				}
				out[out.length] = ']';
				//alert(out);
				break;

			case '+':
				var x = hd[1];
				out[out.length] = re_to_string(x) + '+';
				break;

			case '*':
				var x = hd[1];
				out[out.length] = re_to_string(x) + '*';
				break;
				
			case '?':
				var x = hd[1];
				out[out.length] = re_to_string(x) + '?';
				break;

			case '|':
				var x = hd[1];
				//alert(x);
				var y = hd[2];
				out[out.length] = re_to_string(x) + '|' + re_to_string(y);
				break;
		}
	}
	return out.join('');
};



var lex_empty_action = function(){ };

var lex_re = function(re, action) {
	if (!action) action = lex_empty_action;
	//if (!action) action = function(){};
	
	if (re.constructor === RegExp)
		re = parse_re(re);
	
	//trace(re_to_string(re));
	//trace(dump(re));
	
	var depth = 0;

	var rec = function(re, accept, g) {
		if (!re.length)
			return accept;			
		var hd = re[0];
		var tl = re.slice(1);
		var n = rec(tl, accept, g);
		
		while (hd.length == 1 && is_array(hd[0]))
			hd = hd[0];

		switch (hd[0]) {
			case 'R':
				//alert(hd[1]);
				var x = {};
				var cc = hd[1];
				for (var i = 0, max = cc.length; i < max; ++i)
					x[cc[i]] = n;
				return x;
				
			case 'G':
				var _g = hd[2];
				
				// делаем копию конечного состояния группы
				var m = {};
				objoin(m, n);
				//var m = n;

				var a = rec(hd[1], m, _g);
				return a;

			case 'C':
				var x = {};
				x[hd[1]] = n;
				return x;

			case '.':
				var x = {};
				x.any = n;
				return x;

			case '|':
				var a = rec(hd[1], n, g);
				var b = rec(hd[2], n, g);
				lex_merge(a, b);
				return a;

			case '+':
				var m = objoin({}, n);
				var a = rec(hd[1], m, g);
				lex_merge(m, a);
				return a;

			case '*':
				var m = objoin({}, n);
				var a = rec(hd[1], m, g);
				//alert(dump({ n:n, a:a }));
				lex_merge(m, a);
				return m;

			case '?':
				var a = rec(hd[1], n, g);
				lex_merge(a, n);
				return a;
			}
	};
	//var accept = { action: "RE: " + (re.source || re)};
	action.toString = function(){ return re_to_string(re) };
	var accept = { action: action };
	var x = rec(re, accept);
	return x;
};


var lex_gen = function(l) {
	var actions = [];
	var out = [];
	var rec = function(d, last, l, out, indent) {
		//var indent = str_repeat('    ', d);
		if (l.action) {
			if (l.action.id === undefined)
				actions[l.action.id = actions.length] = l.action;
			last = d;
		}
		for (var j in l) {
			if (j.length != 1 && j != 'any') continue;
			out[out.length] = sprintf('%sC%d: switch (c[i+%d]) {', indent, d, d);
			for (var i in l) {
				if (i.length != 1 && i != 'any') continue;
				if (i == 'any')
					out[out.length] = sprintf('%s    default:', indent);
				else
					out[out.length] = sprintf('%s    case "%s":', indent, js_escape(i));
				rec(d + 1, last, l[i], out, indent + '        ');
			}
			out[out.length] = sprintf('%s}', indent);
			break;
		}
		if (l.action) {
			//out[out.length] = sprintf('%s/* %s: %s */', indent, l.action, Function.prototype.toString.apply(l.action));
			//out[out.length] = sprintf('%sactions[%d]();', indent, l.action.id);
			out[out.length] = sprintf('%s%s;',
				indent,
				trim(Function.prototype.toString.apply(l.action).replace(/^function[^\(\)]*\(\) *{ */, '').replace(/;? *}$/, '').replace(/[ \t]*\n[ \t]*/g, ' '))
			);
			out[out.length] = sprintf('%si += %d;', indent, d);
			out[out.length] = sprintf('%scontinue initial;', indent);
		} else {
			if (last >= 0)
				out[out.length] = sprintf('%sbreak C%d;', indent, last);
		}
	};
	//out[out.length] = 'var count = 0;';
	out[out.length] = 'var i = 0; var max = c.length;';
	out[out.length] = 'initial: while (i < max) {';
	rec(0, -1, l, out, '    ');
	out[out.length] = '}';
	//out[out.length] = 'return count;';
	var code = out.join('\n');
	//trace(code);
	//return code;
	return new Function("c", code);
};







